package algo.A03_递归和算法复杂度;

/**
 * 用递推公式求最大公约数
 * 辗转相除法：求m和n的最大公约数
 * m % n == k，当k==0时，n是最大公约数，否则m = n,n = k
 *
 * 推理:m % n < m/2
 */
public class T06_最大公约数 {
    public static void main(String[] args) {
        int result = solution(144,900);
        System.out.println("result = " + result);
    }

    private static int solution(int m,int n){
        if (m % n == 0){
            return n;
        }
        return solution(n,m % n);
    }
}
